<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 回溯法的核心框架
      // for 选择 in 选择列表:
      // # 做选择
      // 将该选择从选择列表移除
      // 路径.add(选择)
      // backtrack(路径, 选择列表)
      // # 撤销选择
      // 路径.remove(选择)
      // 将该选择再加入选择列表
      var solveNQueens = function (n) {
        // 方法一：回溯（）---时间O（）（不会算，至少是n!，要回溯递归）---空间：O（）（不会算，至少是n，递归栈的深度）
        // const res = [];
        // N皇后2
        let res = 0
        const arr = Array(n)
          .fill([])
          .map(() => Array(n).fill("."));
        backtrack(arr, 0);
        return res;

        function backtrack(arr, row) {
          if (row === arr.length) {
            // res.push(arr.map((item) => item.join('')));
            // N皇后2
            res++
            return;
          }
          for (let col = 0; col < n; col++) {
            if (!isValid(arr, row, col)) {
              continue;
            }
            arr[row][col] = "Q";
            backtrack(arr, row + 1);
            arr[row][col] = ".";
          }
        }

        // 因为皇后是一行一行从上往下放的，所以左下方，右下方和正下方不用检查（还没放皇后）
        // 因为一行只会放一个皇后，所以每行不用检查。也就是最后只用检查上面，左上，右上三个方向。
        function isValid(arr, row, col) {
          // 检查列是否有皇后互相冲突
          for (let i = row; i >= 0; i--) {
            if (arr[i][col] === "Q") {
              return false;
            }
          }
          // 检查左上方是否有皇后互相冲突
          for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (arr[i][j] === "Q") {
              return false;
            }
          }
          // 检查右上方是否有皇后互相冲突
          for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (arr[i][j] === "Q") {
              return false;
            }
          }
          return true
        }
      };

      console.log(solveNQueens(4));
    </script>
  </body>
</html>
